博弈论 2[SG函数]

SGSG函数相关的证明就不说了,直接下定义。

有向图游戏:
把游戏进行中的局面视作一个状态,在当前的状态和进行某些操作后得到的新状态之间连一条有向边,整个图就构成了一个有向图。

MEXMEX函数:
规定MEX(S)MEX(S)是在集合SS中最小的,没有出现的非负整数。

SGSG函数:
在有向图游戏中,从状态xx出去的边有kk条,得到的新状态分别记作y1y_1y2y_2......yky_k,则SG(x)=MEX({SG(y1),SG(y2),......,(SG(yk)})SG(x) = MEX(\{SG(y_1),SG(y_2),......,(SG(y_k)\})。特别的,对于整张图的SGSG函数值为起点的SGSG值。

多个有向图游戏的和:
设共有mm个有向图游戏,记作G1G_1G2G_2,...,GkG_k。每次是在mm个有向图游戏里选一个游戏走一步,记GG是所有有向图游戏的和,则SG(G)=SG(G1)SG(G2),......,SG(Gk)SG(G) = SG(G_1) \bigoplus SG(G_2) \bigoplus,......,\bigoplus SG(G_k)

游戏判据:
有向图游戏的某个局面必胜,当且仅当当前节点的SGSG值大于00
有向图游戏的某个局面必败,当且仅当当前节点的SGSG值为00
对于多个有向图游戏的和,同样满足。

[POJ 2311]Cutting game
题目大意:有一张NMN*M的格子纸,每次可以沿竖直或水平方向的线剪开。第一个剪出大小为11的人胜利。问先手是否必胜。
数据范围:1N,M2001 \leq N,M \leq 200

每次切一下之后,会使得剩下的有向图游戏增多,可以根据上面的多个有向图游戏的和的结论来计算。不过要注意抠掉边界情况,当剩下的局面里有长度为22的条时,就一定失败了。具体在做记忆华搜索的时候,可以通过减少枚举范围来做到。本题的SGSG函数公式也比较显然,这里直接给出:

SG(N,M)=MEX({SG(i,M)SG(Ni,M)}{SG(N,i)SG(N,Mi)})SG(N,M) = MEX(\{SG(i,M) \oplus SG(N - i,M)\} \cup \{SG(N,i) \oplus SG(N,M - i)\})

注意,用于记忆化的数组不必每次都重置,对于某个之前搜过的局面,之后的游戏里如果碰到了不会影响游戏状态。如果每次都重置会导致复杂度过高而TLE。
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
typedef long long ll;
const int N = 205;
int n,m;
int mem[N][N];
int SG(int n,int m)
{
	if(mem[n][m] != -1)	return	mem[n][m];
	set<int> tb;
	
	for(int i = 2;n - i >= 2;++i)	tb.insert(SG(i,m) ^ SG(n - i,m));
	for(int i = 2;m - i >= 2;++i)	tb.insert(SG(n,i) ^ SG(n,m - i));
	
	int res = 0;
	while(tb.count(res))	++res;
	return mem[n][m] = res;
}
int main()
{
	memset(mem,-1,sizeof mem);
	while(scanf("%d%d",&n,&m) == 2)
	{
		if(SG(n,m))	puts("WIN");
		else puts("LOSE");
	}
    return 0;
}